package com.myself.module.source.sort;

import java.util.Arrays;

/**
 * @author 瑟瑟发抖
 * @version 1.0
 * @description 希尔排序
 * @date 2024/4/12 16:11
 */
public class XiErSort {
    //希尔排序 在插入排序基础伤增加步长

    public static int[] sort(int[] input) {
        int b = input.length / 2;
        while (b >= 1) {
            for (int i = 0; i < input.length; i += b) {
                for (int j = i  ; j > b && input[j] < input[j-b]; j -= b) {
                    int middleInt = input[j-b];
                    input[j-b] = input[j];
                    input[j] = middleInt;
                }
            }
            b = b / 2;
        }


        return input;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{1, 8, 9, 5, 4,100,11,12})));
    }
}
